package main

import "sort"

/*
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
*/
func foursum(nums []int, target int) [][]int {
	res := [][]int{}
	counter := map[int]int{}
	//利用map去重数组值，并对key 进行计数
	for _, value := range nums {
		counter[value]++
	}

	uninum := []int{}
	//遍历map的键
	for key := range counter {
		uninum = append(uninum, key)
	}
	//升序排序
	sort.Ints(uninum)
	//a,4=4+0(0+4);4=1+3;4=3+1;4=2+2;4=1+1+1+1
	//锁定变量法，//一个数重复,4=4+0(0+4)
	for i := 0; i < len(uninum); i++ {
		if uninum[i]*4 == target && counter[uninum[i]] >= 4 {
			res = append(res, []int{uninum[i], uninum[i], uninum[i], uninum[i]})
		}
		//两个数字重复,4=1+3;4=3+1;4=2+2;
		for j := i + 1; j < len(uninum); j++ {
			if (uninum[i]*3+uninum[j]) == target && counter[uninum[i]] > 2 {
				res = append(res, []int{uninum[i], uninum[i], uninum[i], uninum[j]})
			}
			if (uninum[j]*3+uninum[i]) == target && counter[uninum[j]] > 2 {
				res = append(res, []int{uninum[i], uninum[j], uninum[j], uninum[j]})
			}
			if (uninum[j]*2+uninum[i]*2) == target && counter[uninum[j]] > 1 && counter[uninum[i]] > 1 {
				res = append(res, []int{uninum[i], uninum[i], uninum[j], uninum[j]})
			}
			//三个数字重复,4=1+1+2,4=1+2+1;4=2+1+1
			for k := j + 1; k < len(uninum); k++ {
				if (uninum[i]+uninum[j]+uninum[k]*2) == target && counter[uninum[k]] > 1 {
					res = append(res, []int{uninum[i], uninum[j], uninum[k], uninum[k]})
				}
				if (uninum[i]+uninum[j]*2+uninum[k]) == target && counter[uninum[j]] > 1 {
					res = append(res, []int{uninum[i], uninum[j], uninum[j], uninum[k]})
				}
				if (uninum[i]*2+uninum[j]+uninum[k]) == target && counter[uninum[i]] > 1 {
					res = append(res, []int{uninum[i], uninum[i], uninum[j], uninum[k]})
				}

				//4=1+1+1+1,把任意三个数字放到map里，降低了复杂度
				c := 0 - uninum[i] - uninum[j] - uninum[k]
				//存在这个数字并且，在升序数列的后面（即还没有遍历过的）
				if counter[c] > 0 && c > uninum[k] {
					res = append(res, []int{uninum[i], uninum[j], uninum[k], c})
				}
			}
		}
	}
	return res
}
